package immutablecollections;

import immutablecollections.exceptions.*;
import immutablecollections.functions.*;
import immutablecollections.misc.*;
import java.util.*;

/**
 * A zipper on an {@link ImRoseTree} lets you navigate back and forth in the tree and "mutate" it as you go.
 * 
 * ### Introduction
 * 
 * In general, zippers on immutable data structures allow you to move around the data structure, making local
 * modifications efficiently and only making the complete new structure when you use {@link #close()}.
 * 
 * Recall that a rose tree has a root node containing an element and an ordered list (shelf) of sub-trees.
 * The definition is recursive - each sub-tree
 * also has an element and a shelf of
 * sub-trees and so on. Leaf trees are those with no sub-trees - ie their shelf is empty.
 * 
 * A zipper on a rose tree with focus at node `n` is recursively defined as:
 * 
 * 1. a shelf zipper on `n`'s parent sub-trees, focussed on `n`
 * 2. a reference to the rose tree zipper for `n`'s parent.
 * 
 * The first shelf zipper as defined above is called the *current* shelf zipper.
 * 
 * In this tree:
 * 
 *     1      
 *     .......
 *     2 3   6
 *       ...  
 *       4 5 
 *       
 * a zipper on the node with element 5 would be:
 * 
 * 1. a shelf zipper on shelf [4, 5] with the focus on 5 and a reference its parent which is
 * 2. a shelf zipper on shelf [2, 3, 6] with the focus on 3 and a reference its parent which is
 * 3. a shelf zipper on shelf [1] with the focus on 1 and no parent
 * 
 * In this example the current shelf zipper is 1. above.
 * 
 * (The shelf zipper on the root is really an implementation detail - we consider the root tree to be in a shelf of size 1)
 * 
 * The {@link #toString()} method would show it like this:
 * 
 *     [1] [] <- [2, 3] [6] <- [4] [5]
 * 
 * ### Example
 * 
 * So to mutate node 4 in the example above you could do this:
 * 
 *     tree.getZipper().next().next().next().setElement(7).close()
 *     
 * Which would generate the tree:
 * 
 *     1      
 *     .......
 *     2 3   6
 *       ...  
 *       7 5  
 * 
 * ### Navigation
 * 
 * The API to the rose tree zipper is somewhat similar to {@link ImListZipper} but with some differences:
 * 
 * 1. These methods:
 * 
 *  * {@link #next()}
 *  * {@link #prev()}
 *  * {@link #hasNext()}
 *  * {@link #hasPrev()}
 *  
 *  work on the tree as a whole (rather than just one shelf of sub-trees).
 *  `next()` on a tree that has sub-trees will move to the first sub-tree; otherwise, if
 *  it has a next sibling node, it will move to that; otherwise it will recursively try to move next on the parent.
 *  This means that repeated calls to `next(`) will iterate over the whole tree.
 *  
 *  If you use `prev()` on a zipper at the first tree in its parent's shelf then it will return the parent rather
 *  than a shelf in the initial state.
 *  
 *  `next()` and `prev()` will always return a zipper that has a focus. 
 *  
 *  These methods:
 *  
 *  * {@link #nextSibling()}
 *  * {@link #prevSibling()}
 *  * {@link #hasNextSibling()}
 *  * {@link #hasPrevSibling()}
 *  
 * work on the shelf that contains the focus (rather than the whole tree) and operate exactly like a shelf zipper.
 *  
 * To move to the parent tree you can use  {@link #up()} and to move down to the sub-trees you
 * can use  {@link #down()} - which moves to *before* the first sub-tree.
 * 
 * Just as with {@link ImShelf#next()}, {@link #prevSibling()} will sometimes return a zipper that has no focus.
 * 
 * See the <a href="{@docRoot}/immutablecollections/package-summary.html">package summary</a>
 * for more details about zippers.

 * @see ImRoseTree
 * @see ImRoseTreeIterator
 * @see ImRoseTreeZipperIterator
 * @see ImShelfZipper
 *
 */
public class ImRoseTreeZipper<T> implements Iterable<ImRoseTreeZipper<T>>
{
    final private ImShelfZipper<ImRoseTree<T>> zipper;
    final private ImRoseTreeZipper<T> parent;

    ImRoseTreeZipper(ImShelfZipper<ImRoseTree<T>> zipper, ImRoseTreeZipper<T> parent)
    {
        this.zipper = zipper;
        this.parent = parent;
    }

    /**
     * A zipper on `tree` with the focus on the root node.
     */
    ImRoseTreeZipper(ImRoseTree<T> tree)
    {
        this(ImShelf.on(tree).getZipperOnIndex(1), null);
    }

    /**
     * The zipper that is the same as `this` except that the focus is `newTree`.
     * 
     * @throws NoSuchElementException if there is no focus
     */
    public ImRoseTreeZipper<T> setFocus(ImRoseTree<T> newTree)
    {
        return new ImRoseTreeZipper<T>(zipper.setFocus(newTree), parent);
    }

    /**
     * The "parent" zipper - incorporating any changes made to the current shelf.
     * 
     * `up()` calls close() on the current shelf so that the
     * parent zipper focus will be a tree that incorporates any mutations that you
     * made to the sub-trees.
     * 
     * This:
     * 
     *     ImRoseTree<Integer> tree = ImRoseTree.withNodes(1, leaf(2), ImRoseTree.withElements(3, 4, 5), leaf(6));
     * 
     * will create a tree like this:
     * 
     *     1      
     *     .......
     *     2 3   6
     *       ...  
     *       4 5 
     *       
     * If we get a zipper on node `3`:
     * 
     *     ImRoseTreeZipper<Integer> z = tree.getZipper();
     *     ImRoseTreeZipper<Integer> z3 = z.next().next();
     * 
     * and then get a zipper on node `4`:
     *  
     *     ImRoseTreeZipper<Integer> z4 = z3.next();
     * 
     * If we go up from `z4` without making changes we merely get `z3`
     * 
     *     z4.up() == z3  =>  "true"
     *     
     * but if we make changes ... we don't
     * 
     *     z4.setElement(7).up() == z3  => "false"
     * 
     * @throws NoSuchElementException if the zipper is focussed on the root node
     */
    public ImRoseTreeZipper<T> up()
    {
        if (isRoot())
            throw new NoSuchElementException(); // TODO fix
        else
        {
            ImShelf<ImRoseTree<T>> newShelf = zipper.close();

            // If the new shelf is the same as my parent node shelf then nothing has changed
            return newShelf == parent.getFocus().getSubTrees()
                    ? parent
                    : parent.setFocus(ImRoseTree.withNodes(parent.getFocus().getElement(), newShelf));
        }
    }

    public boolean isRoot()
    {
        return parent == null;
    }

    /**
     * The focus of the zipper.
     *     
     * @throws ZipperHasNoFocusException if there is no focus
     */
    public ImRoseTree<T> getFocus()
    {
        if (zipper.getFocus() == null)
            throw new ZipperHasNoFocusException();
        else
            return zipper.getFocus();
    }

    /**
     * The underlying tree, with all modifications made.
     *
     * If no modifications have been made then the original tree is returned.
     */
    public ImRoseTree<T> close()
    {
        if (isRoot())
            if (zipper.getIndex() == 0)
                throw new RuntimeException();
            else
                return zipper.getFocus();
        else
            return up().close();
    }

    /**
     * The zipper whose focus is the next node in the tree.
     * 
     * If the node has sub-trees then the next node is the first sub-tree.
     * 
     * If the focus is a leaf node, then the next node is the next sibling node, if it exists. If
     * no such sibling node exists we ask the zipper obtained from from `up()` for the next sibling node and
     * continue recursively
     * until one is found or we reach the root.
     * 
     * @throws NoSuchElementException if no such node exists
     * @see #hasNext()
     * @see #prev()
     * @see #nextSibling()
     */
    public ImRoseTreeZipper<T> next()
    {
        return getFocus().getSubTrees().isEmpty()
                ? nextAlong()
                : down().nextSibling();
    }

    /**
     * The zipper with the current shelf on the sub-trees of the focus, positioned
     * before the first sub-tree, if there is one.
     * 
     * @see #up()
     */
    public ImRoseTreeZipper<T> down()
    {
        return new ImRoseTreeZipper<T>(getFocus().getSubTrees().getZipper(), this);
    }

    private ImRoseTreeZipper<T> nextAlong()
    {
        if (zipper.hasNext())
            return new ImRoseTreeZipper<T>(zipper.next(), parent);
        else if (isRoot())
            throw new NoSuchElementException(); // TODO fix
        else
            return up().nextAlong();
    }

    /**
     * Get the element of the tree at the focus.
     * 
     * @see #getFocus
     */
    public T getElement()
    {
        return getFocus().getElement();
    }

    /**
     * Set the element of the tree at the focus leaving its sub-trees unchanged.
     * 
     * @see #getElement()
     */
    public ImRoseTreeZipper<T> setElement(T newElement)
    {
        return setFocus(getFocus().replaceElement(newElement));
    }

    /**
     * The zipper that is the same as `this` but with the last node popped from the first list of the current shelf
     * zipper.
     * 
     * @throws UnsupportedOperationException if the focus of `this` is the root of the tree
     */
    public ImRoseTree<T> pop()
    {
        if (isRoot())
            throw new UnsupportedOperationException("attempt to remove root node");

        return new ImRoseTreeZipper<T>(zipper.pop(), parent).close();
    }

    /**
     * Push `treeToInsert` before the focus node.
     * 
     * For all `z` and `t`:
     * 
     *     z.pushBefore(t) == z.prevSibling().push(t)
     * 
     * @throws UnsupportedOperationException if the focus of `this` is the root of the tree
     * @see #push(ImRoseTree)
     * @see #prevSibling()
     */
    public ImRoseTreeZipper<T> pushBefore(ImRoseTree<T> treeToInsert)
    {
        if (isRoot())
            throw new UnsupportedOperationException("Zipper is at the root of the tree");
        else
            return new ImRoseTreeZipper<T>(zipper.prev().push(treeToInsert), parent);
    }

    /**
     * The zipper that is the same as `this` but with `treeToInsert` pushed onto the first list of the current shelf
     * zipper.
     * 
     * The new focus is `treeToInsert`.
     * 
     * @throws UnsupportedOperationException if the focus of `this` is the root of the tree
     */
    public ImRoseTreeZipper<T> push(ImRoseTree<T> treeToInsert)
    {
        if (isRoot())
            throw new UnsupportedOperationException("Zipper is at the root of the tree");
        else
            return new ImRoseTreeZipper<T>(zipper.push(treeToInsert), parent);
    }

    /**
     * `true` if the focus has a next , `false` otherwise.
     * 
     * @see #next()
     */
    public boolean hasNext()
    {
        return getFocus().getSubTrees().isEmpty()
                ? hasNextAlong()
                : true;
    }

    private boolean hasNextAlong()
    {
        return zipper.hasNext()
                ? true
                : isRoot()
                        ? false
                        : parent.hasNextAlong();
    }

    /**
     * The string representation of this zipper.
     * 
     * Each shelf zipper at each level is shown - the parent zipper shown before the child
     * 
     * For clarity, to display each zipper we use its {@link ImShelfZipper#toString(Function1)} method and
     * we use a display function {@link #rootToStringFn} that shows *just the root element of the tree* (rather than using
     * {@link ImRoseTree#toString()} which would show the whole tree)
     * 
     * So - using this tree:
     * 
     *     1      
     *     .......
     *     2 3   6
     *       ...  
     *       4 5  
     *       
     * If we  get a zipper on it and then repeatedly use `next().toString()` we would get this:
     * 
     *     [1] []
     *     [1] [] <- [2] [3, 6]
     *     [1] [] <- [2, 3] [6]
     *     [1] [] <- [2, 3] [6] <- [4] [5]
     *     [1] [] <- [2, 3] [6] <- [4, 5] []
     *     [1] [] <- [2, 3, 6] []
     * 
     */
    @Override
    public String toString()
    {
        return toString(rootToStringFn);
    }

    // The toString(fn) function in the shelf zipper that takes a function arguments
    static Function2<String> toStringFn = FnFactory.on(ImShelfZipper.class).getFn(String.class, "toString",
            Function1.class);

    /**
     * A string representation of this zipper that uses the function `fn` on each tree to get its string representation.
     * 
     * @see immutablecollections.functions
     */
    public String toString(Function1<String> fn)
    {
        return TextUtils.join(getAllShelfZippers().reversed().map(toStringFn.flip().invoke(fn)), " <- ");
    }

    // The function that gets the string representation of the root of a tree
    Function1<String> rootToStringFn = FnFactory.on(ImRoseTreeZipper.class).getFnStatic( //
            String.class, "rootToString", ImRoseTree.class);

    /**
     * The method used by {@link #toString()} to display tree nodes.
     */
    public static String rootToString(ImRoseTree<String> tree)
    {
        return tree.getElement().toString();
    }

    private ImList<ImShelfZipper<ImRoseTree<T>>> getAllShelfZippers()
    {
        return isRoot()
                ? ImList.on(zipper)
                : ImList.cons(zipper, parent.getAllShelfZippers());
    }

    /**
     * An {@link ImRoseTreeZipperIterator#} on `this`
     */
    @Override
    public Iterator<ImRoseTreeZipper<T>> iterator()
    {
        return new ImRoseTreeZipperIterator<T>(this);
    }

    /**
     * `true` if the focus has a previous node, `false` otherwise.
     * 
     * @see #prev()
     */
    public boolean hasPrev()
    {
        return parent != null;
    }

    /**
     * The zipper whose focus is the previous node in the tree.
     * 
     * If the node has no previous sibling then the zipper obtained from from `up()`
     * is returned if one exists.
     * 
     * If the node has a previous sibling then, if it is a leaf node, then it is returned.
     * 
     * Otherwise we return the previous node's last sub-tree node, if it is a leaf node, or continue
     * recursively searching its sub-trees until we find a leaf node.
     * 
     * @throws NoSuchElementException if the focus of `this` is the root of the tree
     * @see #hasPrev()
     * @see #next()
     * @see #prevSibling()
     */
    public ImRoseTreeZipper<T> prev()
    {
        if (zipper.hasPrev())
            return new ImRoseTreeZipper<T>(zipper.prev(), parent).goDownLast();
        else
            return up();
    }

    private ImRoseTreeZipper<T> goDownLast()
    {
        ImShelf<ImRoseTree<T>> subTrees = getFocus().getSubTrees();

        return subTrees.isEmpty()
                ? this
                : new ImRoseTreeZipper<T>(subTrees.getZipperOnIndex(subTrees.size()), this).goDownLast();
    }

    /**
     * The next sibling node, if there is one.
     * 
     * @throws NoSuchElementException if the current shelf zipper does not have a next node
     * @see #hasNextSibling()
     */
    public ImRoseTreeZipper<T> nextSibling()
    {
        if (isRoot())
            throw new NoSuchElementException("Zipper is at the root of the tree");
        else if (!zipper.hasNext())
            throw new NoSuchElementException("Zipper is at the end of the sub-trees shelf");
        else
            return new ImRoseTreeZipper<T>(zipper.next(), parent);
    }

    /**
     * `true` if the focus has a next sibling node, `false` otherwise.
     * 
     * @see #nextSibling()
     */
    public boolean hasNextSibling()
    {
        return zipper.hasNext();
    }

    /**
     * The previous sibling node, if there is one.
     * 
     * @throws NoSuchElementException if the focus of `this` is the root of the tree
     * @see #hasPrevSibling()
     */
    public ImRoseTreeZipper<T> prevSibling()
    {
        if (isRoot())
            throw new NoSuchElementException("Zipper is at the root of the tree");
        else
            return new ImRoseTreeZipper<T>(zipper.prev(), parent);
    }

    /**
     * `true` if the focus has a previous sibling node, `false` otherwise.
     * 
     * @see #prevSibling()
     */
    public boolean hasPrevSibling()
    {
        return zipper.hasPrev();
    }

}
